use std::ptr::null_mut;
const TRIE_NULL: *mut std::ffi::c_void = null_mut();
type TrieValue = *mut std::ffi::c_void;
#[repr(C)]
struct TrieNode {
    pub data: TrieValue,
    pub use_count: u32,
    pub next: [*mut TrieNode; 256],
}
#[repr(C)]
struct Trie {
    pub root_node: *mut TrieNode,
}
fn trie_new() -> *mut Trie {
    unsafe {
        let new_trie = malloc(std::mem::size_of::<Trie>()) as *mut Trie;
        if new_trie.is_null() {
            return ptr::null_mut();
        }
        (*new_trie).root_node = ptr::null_mut();
        new_trie
    }
}
fn trie_free_list_push(list: &mut Option<Box<TrieNode>>, node: Box<TrieNode>) {
    let mut node = node;
    node.data = list.take();
    *list = Some(node);
}
fn trie_free_list_pop(list: &mut *mut TrieNode) -> *mut TrieNode {
    let result = *list;
    if !result.is_null() {
        *list = unsafe { (*result).data };
    }
    result
}
fn trie_free(trie: *mut Trie) {
    let mut free_list: *mut TrieNode = std::ptr::null_mut();
    let mut node: *mut TrieNode;
    let mut i: usize;
    unsafe {
        if !(*trie).root_node.is_null() {
            trie_free_list_push(&mut free_list, (*trie).root_node);
        }
        while !free_list.is_null() {
            node = trie_free_list_pop(&mut free_list);
            for i in 0..256 {
                if !(*node).next[i].is_null() {
                    trie_free_list_push(&mut free_list, (*node).next[i]);
                }
            }
            libc::free(node as *mut libc::c_void);
        }
        libc::free(trie as *mut libc::c_void);
    }
}
fn trie_find_end(trie: &Trie, key: &str) -> *mut TrieNode {
    let mut node = trie.root_node;
    for &p in key.as_bytes() {
        if node.is_null() {
            return std::ptr::null_mut();
        }
        unsafe {
            node = (*node).next[p as usize];
        }
    }
    node
}
fn trie_find_end_binary<'a>(
    trie: &'a Trie,
    key: &'a [u8],
    key_length: usize,
) -> Option<&'a TrieNode> {
    let mut node = trie.root_node.as_ref();
    for j in 0..key_length {
        node = match node {
            Some(n) => n.next[key[j] as usize].as_ref(),
            None => return None,
        };
    }
    node
}
fn trie_insert_rollback(trie: &mut Trie, key: *const u8) {
    let mut node: *mut TrieNode;
    let mut prev_ptr: *mut *mut TrieNode;
    let mut next_node: *mut TrieNode;
    let mut next_prev_ptr: *mut *mut TrieNode;
    let mut p: *const u8;
    node = trie.root_node;
    prev_ptr = &mut trie.root_node;
    p = key;
    unsafe {
        while !node.is_null() {
            next_prev_ptr = &mut (*node).next[*p as usize];
            next_node = *next_prev_ptr;
            p = p.add(1);
            (*node).use_count -= 1;
            if (*node).use_count == 0 {
                libc::free(node as *mut libc::c_void);
                if !prev_ptr.is_null() {
                    *prev_ptr = null_mut();
                }
                next_prev_ptr = null_mut();
            }
            node = next_node;
            prev_ptr = next_prev_ptr;
        }
    }
}
fn trie_insert(trie: &mut Trie, key: &str, value: TrieValue) -> i32 {
    let mut rover: *mut *mut TrieNode;
    let mut node: *mut TrieNode;
    let mut p: *const u8;
    let mut c: u8;
    if value.is_null() {
        return 0;
    }
    node = unsafe { trie_find_end(trie, key) };
    if !node.is_null() && unsafe { (*node).data } != std::ptr::null_mut() {
        unsafe {
            (*node).data = value;
        }
        return 1;
    }
    rover = &mut trie.root_node;
    p = key.as_ptr();
    loop {
        node = unsafe { *rover };
        if node.is_null() {
            node = unsafe { libc::calloc(1, std::mem::size_of::<TrieNode>()) as *mut TrieNode };
            if node.is_null() {
                unsafe {
                    trie_insert_rollback(trie, key.as_ptr());
                }
                return 0;
            }
            unsafe {
                (*node).data = std::ptr::null_mut();
            }
            unsafe {
                *rover = node;
            }
        }
        unsafe {
            (*node).use_count += 1;
        }
        c = unsafe { *p };
        if c == 0 {
            unsafe {
                (*node).data = value;
            }
            break;
        }
        rover = unsafe { &mut (*node).next[c as usize] };
        p = unsafe { p.add(1) };
    }
    1
}
fn trie_insert_binary(trie: &mut Trie, key: &mut [u8], key_length: usize, value: TrieValue) -> i32 {
    let mut rover: *mut *mut TrieNode;
    let mut node: *mut TrieNode;
    let mut p: usize;
    let mut c: u8;
    if value.is_null() {
        return 0;
    }
    node = unsafe { trie_find_end_binary(trie, key.as_mut_ptr(), key_length) };
    if !node.is_null() && unsafe { (*node).data } != TRIE_NULL {
        unsafe { (*node).data = value };
        return 1;
    }
    rover = &mut trie.root_node;
    p = 0;
    loop {
        node = unsafe { *rover };
        if node.is_null() {
            node = unsafe { libc::calloc(1, std::mem::size_of::<TrieNode>()) as *mut TrieNode };
            if node.is_null() {
                unsafe { trie_insert_rollback(trie, key.as_mut_ptr()) };
                return 0;
            }
            unsafe { (*node).data = TRIE_NULL };
            unsafe { *rover = node };
        }
        unsafe { (*node).use_count += 1 };
        c = key[p];
        if p == key_length {
            unsafe { (*node).data = value };
            break;
        }
        rover = unsafe { &mut (*node).next[c as usize] };
        p += 1;
    }
    1
}
fn trie_remove_binary(trie: *mut Trie, key: *mut u8, key_length: i32) -> i32 {
    let mut node: *mut TrieNode;
    let mut next: *mut TrieNode;
    let mut last_next_ptr: *mut *mut TrieNode = 0 as *mut *mut TrieNode;
    let mut p = 0;
    let mut c;
    unsafe {
        node = trie_find_end_binary(trie, key, key_length);
        if !node.is_null() && (*node).data != TrieValue::Null {
            (*node).data = TrieValue::Null;
        } else {
            return 0;
        }
        node = (*trie).root_node;
        last_next_ptr = &mut (*trie).root_node;
        p = 0;
        loop {
            c = *key.offset(p as isize) as usize;
            next = (*node).next[c];
            (*node).use_count -= 1;
            if (*node).use_count == 0 {
                libc::free(node as *mut libc::c_void);
                if !last_next_ptr.is_null() {
                    *last_next_ptr = std::ptr::null_mut();
                    last_next_ptr = std::ptr::null_mut();
                }
            }
            if p == key_length {
                break;
            } else {
                p += 1;
            }
            if !last_next_ptr.is_null() {
                last_next_ptr = &mut (*node).next[c];
            }
            node = next;
        }
        1
    }
}
fn trie_remove(trie: &Trie, key: *const c_char) -> i32 {
    unsafe {
        let mut node: *mut TrieNode;
        let mut next: *mut TrieNode;
        let mut last_next_ptr: *mut *mut TrieNode;
        let mut p = key;
        let mut c: i32;
        node = trie_find_end(trie, key);
        if !node.is_null() && (*node).data != TRIE_NULL {
            (*node).data = TRIE_NULL;
        } else {
            return 0;
        }
        node = trie.root_node;
        last_next_ptr = &mut trie.root_node;
        while *p != 0 {
            c = *p as u8 as i32;
            next = (*node).next[c as usize];
            (*node).use_count -= 1;
            if (*node).use_count <= 0 {
                libc::free(node as *mut libc::c_void);
                if !last_next_ptr.is_null() {
                    *last_next_ptr = ptr::null_mut();
                    last_next_ptr = ptr::null_mut();
                }
            }
            if c == 0 {
                break;
            } else {
                p = p.offset(1);
            }
            if !last_next_ptr.is_null() {
                last_next_ptr = &mut (*node).next[c as usize];
            }
            node = next;
        }
        1
    }
}
fn trie_lookup(trie: &Trie, key: &str) -> TrieValue {
    let node = trie_find_end(trie, key);
    if let Some(node) = node {
        node.data
    } else {
        TRIE_NULL
    }
}
fn trie_lookup_binary(trie: &Trie, key: &[u8], key_length: i32) -> TrieValue {
    let node = trie_find_end_binary(trie, key, key_length);
    if !node.is_null() {
        unsafe { (*node).data }
    } else {
        TRIE_NULL
    }
}
fn trie_num_entries(trie: &Trie) -> u32 {
    if let Some(entry) = trie.get_entry() {
        entry.count
    } else {
        0
    }
}
